package com.zklh.leetcode.structure.monotonestack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 环形 下一个更大的元素算法实现 相对于1, 就是变成翻倍的Nums, 然后结果也翻倍, 但是取一半
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/7/25 17:23
 */
public class NextGreaterElements2 {



    public int[] nextGreaterElements(int[] nums) {

        int[] result = new int[nums.length*2];
        Deque<Integer> stack = new LinkedList<>();

        for (int i = nums.length * 2 - 1; i >= 0; i--) {
            // 为了不扩容 通过point 实现
            int point = i > nums.length-1 ? i-nums.length : i;

            while (!stack.isEmpty() && stack.getFirst() <= nums[point]) {
                stack.poll();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[point]);
        }


        return Arrays.copyOf(result, nums.length);
    }

    public static void main(String[] args) {
        NextGreaterElements2 nextGreaterElements2 = new NextGreaterElements2();
        System.out.println(Arrays.toString(nextGreaterElements2.nextGreaterElements(new int[]{2, 1, 2, 4, 3})));
    }
}
